package leetcode.f1t100;

/**
 * 给一串数字, 数字代表可向后跳的步数, 判断是否可以调到尾部
 * https://leetcode.com/problems/jump-game/
 * @Author lichongxiao
 * @Date 2022/10/25 10:37
 */
public class Q55_JumpGame {
    public boolean canJump(int[] nums) {
        return canJumpGreedy(nums);
    }

    private boolean canJumpGreedy(int[] nums){
        int curEnd = 0;
        for (int i = 0; i < nums.length; i++) {
            curEnd = Math.max(curEnd, nums[i]+i);
            if(curEnd >= nums.length-1){
                return true;
            }
            if(i == curEnd && nums[i] == 0){
                return false;
            }
        }
        return false;
    }

    private boolean canJumpdp(int[] nums){
        boolean[] dp = new boolean[nums.length];
        dp[nums.length-1] = true;
        for (int i = nums.length-2; i >=0 ; i--) {
            for (int j = 1; j <= nums[i] && i+j<nums.length; j++) {
                dp[i] |= dp[i+j];
            }
        }
        return dp[0];
    }

}

